package com.agile.leetcode.node.swapnode;


/**
 * 给你链表的头节点 head 和一个整数 k 。
 * <p>
 * 交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[1,4,3,2,5]
 * <p>
 * 示例 2：
 * <p>
 * 输入：head = [7,9,6,6,7,8,3,0,9,5], k = 5
 * 输出：[7,9,6,6,8,7,3,0,9,5]
 * <p>
 * 示例 3：
 * <p>
 * 输入：head = [1], k = 1
 * 输出：[1]
 * <p>
 * 示例 4：
 * <p>
 * 输入：head = [1,2], k = 1
 * 输出：[2,1]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/swapping-nodes-in-a-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author KD
 * @Date 2021/2/25 15:31
 */
public class SwapNode {
    public static void main(String[] args) {
        ListNode node5 = new ListNode(5, null);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
        SwapNode swapNode = new SwapNode();
        ListNode node = swapNode.swapNode(node1, 2);
        System.out.println(node);
        System.out.println(swapNode.swapNode_1(node, 4));
    }

    public ListNode swapNode(ListNode head, int k) {
        //
        ListNode current = head;
        ListNode kNode = current;
        ListNode lastKNode = current;
        // 计数器
        int i = 1;
        // 定义值接收
        int value = Integer.MIN_VALUE;
        int lastValue = Integer.MIN_VALUE;
        while (current != null) {
            // 判断是否是当前节点
            if (i == k) {
                // 拿到当前值
                value = current.val;
                kNode = current;
            }
            // 判断是否是最后k
            if (lastValue == Integer.MIN_VALUE && isLastKNode(current, k)) {
                // 拿到当前值
                lastValue = current.val;
                lastKNode = current;
            }
            if (value != Integer.MIN_VALUE && lastValue != Integer.MIN_VALUE) {
                // 找到值
                kNode.val = lastValue;
                lastKNode.val = value;
                break;
            }
            current = current.next;
            i++;
        }
        return head;
    }

    public ListNode swapNode_1(ListNode head, int k) {
        ListNode current = head;
        ListNode pre = current;
        ListNode last = current;
        boolean preFlag = false;
        boolean lastFlag = false;
        int i = 1;
        while (current != null) {
            if (i == k) {
                // 第k个几点
                pre = current;
                preFlag = true;
            }
            // 找到后就不能进去，不然要空指针
            if (!lastFlag&&isLastKNode(current, k)) {
                last = current;
                lastFlag = true;
            }
            if (preFlag && lastFlag) {
                break;
            }
            current = current.next;
            i++;
        }
        // 交换值
        int value = pre.val;
        int lastValue = last.val;
        pre.val = lastValue;
        last.val = value;
        return head;
    }

    /**
     * 判断是否是倒数的第K个节点
     *
     * @param node
     * @param k
     * @return
     */
    public boolean isLastKNode(ListNode node, int k) {
        for (int i = 0; i < k; i++) {
            node = node.next;
        }
        return node == null;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}
